package com.hanxiaozhang.no3algorithm.backtrack;

import java.util.Arrays;

/**
 * 〈一句话功能简述〉<br>
 * 〈N皇后〉
 *
 * @author hanxinghua
 * @create 2023/10/27
 * @since 1.0.0
 */
public class No1NQueen {


    public static void main(String[] args) {
        queen1(4);
        queen2(4);
    }


    /**
     * 非递归
     *
     * @param n
     */
    public static void queen1(Integer n) {

        // 设置结果数据数组，默认值都为0，索引为0位置不使用
        int[] q = new int[n + 1];

        // 表示正在摆放第j个皇后
        int j = 1;
        // 处理
        while (j >= 1) {
            // 让第j个皇后向后一列摆放
            q[j] = q[j] + 1;
            // 判断第j个皇后的位置是否合法，不合法就往后一个位置摆放，直到摆放的最后一个位置结束。
            while (q[j] <= n && !check(q, j)) {
                // 不合法就往后一个位置摆放
                q[j] = q[j] + 1;
            }
            // 表示第j个皇后的找到一个合法的摆放位置时
            if (q[j] <= n) {
                // N皇后，到了最后一组的解，保存答案。
                if (j == n) {
                    print(q);
                } else {
                    // 继续摆放下一个皇后
                    j = j + 1;
                }
            } else {
                // 表示第j个皇后找不到一个合法的摆放位置时，
                // 将还原第j个皇后的位置为0
                q[j] = 0;
                // 回溯到上一个j。
                j = j - 1;
            }
        }
    }


    /**
     * 递归
     *
     * @param n
     */
    public static void queen2(Integer n) {
        // 设置结果数据，默认值为0
        int[] q = new int[n + 1];
        queenSub(1, n, q);
    }

    public static void queenSub(int j, int n, int[] q) {

        for (int i = 1; i <= n; i++) {
            q[j] = i;
            // 当摆放的皇后位置为合法时
            if (check(q, j)) {
                // 找到了 N 皇后的一组解
                if (j == n) {
                    print(q);
                } else {
                    // 递归摆放下一个皇后的位置
                    queenSub(j + 1, n, q);
                }
            }
        }
    }

    /**
     * 判断 两个皇后是否存在同一列 和  两个皇后是否存在同一斜线
     *
     * @param q 结果数组
     * @param j 添加元素位置
     * @return
     */
    private static boolean check(int[] q, int j) {

        for (int i = 1; i < j; i++) {
            if (q[i] == q[j] || Math.abs(q[i] - q[j]) == j - i) {
                return false;
            }
        }
        return true;
    }


    private static void print(int[] q) {
        int[] a = new int[q.length - 1];
        for (int i = 1; i < q.length; i++) {
            a[i - 1] = q[i];
        }
        System.out.println(Arrays.toString(a));
    }

}
